#include <cpp_primer.h>

using namespace std;

int operatorProcedence(const char op);
int calculate(int num1, int num2, char op);
int evaluateExpression(const string &expr);

int main()
{
    string expr("(1 - 2) * 2 * 3");
    try {
        cout << evaluateExpression(expr) << endl;

    } catch (exception &ex) {
        cerr << ex.what() << endl;

    }

    return 0;

}

int operatorProcedence(const char op)
{
    if(op == '+' || op == '-')
        return 1;
    else if(op == '*' || op == '/')
        return 2;
    else if(op == '(' || op == ')')
        return 0;
    else
        throw invalid_argument("Invalid operator");

}

int calculate(int num1, int num2, char op)
{
    switch (op) {
    case '+':   return (num1 + num2);
    case '-':   return (num1 - num2);
    case '*':   return (num1 * num2);
    case '/':
                if(num2 == 0)
                    throw runtime_error("Division by zero");
                return (num1 / num2);
    default:    throw runtime_error("calculate function error");

    }

}

int evaluateExpression(const string &expr)
{
    stack<int> num_stack;
    stack<char> op_stack;

    auto it = expr.begin();
    while(it != expr.end()) {
        // 跳过空格
        if(isspace(*it)) {
            ++it;
            continue;
        }
        // 数字入数字栈
        // 只有一种情况是减号，前一个是数字或者)
        if(isdigit(*it) || (*it == '-' && (*(it - 1) == ')' || isdigit(*(it - 1))))) {
            int num = 0;
            int sign = 1;
            // 处理负数
            if(*it == '-'){
                sign = -1;
                ++it;
            }

            while(isdigit(*it)) {
                num = num * 10 + (*it - '0');
                ++it;
            }
            num_stack.push(num * sign);
        }
        // 左右括号
        else if(*it == '(') {
            op_stack.push(*it++);
        }
        // 右括号，出栈
        else if (*it == ')') {
            while(!op_stack.empty() && op_stack.top() != '(') {
                // 右操作符
                int num2 = num_stack.top();
                num_stack.pop();
                // 左操作符
                int num1 = num_stack.top();
                num_stack.pop();
                // 结果入栈,符号出栈
                num_stack.push(calculate(num1, num2, op_stack.top()));
                op_stack.pop();
            }
            // 括号不匹配
            if(op_stack.top() != '(')
                throw invalid_argument("Mismatched parentheses");
            else {
                op_stack.pop();
                ++it;
            }
        }
        // 四则运算符
        else {
            // 处理优先级
            while(!op_stack.empty() && operatorProcedence(op_stack.top()) >= operatorProcedence(*it)) {
                // 右操作符
                int num2 = num_stack.top();
                num_stack.pop();
                // 左操作符
                int num1 = num_stack.top();
                num_stack.pop();
                // 结果入栈，符号出栈，继续下次循环
                num_stack.push(calculate(num1, num2, op_stack.top()));
                op_stack.pop();
            }
            // 循环以后，c优先级最高，入栈
            op_stack.push(*it++);
        }
    }
    // 处理剩余
    while(!op_stack.empty()) {
        if(op_stack.top() == '(')
            throw invalid_argument("Mismatched parentheses");

        // 右操作符
        int num2 = num_stack.top();
        num_stack.pop();
        // 左操作符
        int num1 = num_stack.top();
        num_stack.pop();
        // 结果入栈,符号出栈
        num_stack.push(calculate(num1, num2, op_stack.top()));
        op_stack.pop();
    }

    if (num_stack.size() != 1 || !op_stack.empty()) {
        throw std::runtime_error("Invalid expression");
    }

    return num_stack.top();
}
